package com.example.demo.algorithms;

/**
 * <p>Description: 整齐打印算法</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/4/11 22:52
 **/
public class PrintNeatly {
    /**
     * @param A A[i]表示第i个字符的长度
     * @param M 每行最多字符个数
     * @return
     */
    public int getNeatly(int[] A, int M) {
        int len = A.length;
        int[][] W = new int[len][len]; // W[i][j] 表示 i 到 j 单词所在行的末尾空格数
        int[] B = new int[len];// B[i] 表示 0 到i内单词最优空格立方总和
        int[] rowStartIndex = new int[len];// C[i] 表示每行的开始位置
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {// 只保存上三角元素
                int w = M - j + i;
                for (int k = i; k <= j; k++) {
                    w -= A[k];
                }
                w = (int) Math.pow(w, 3);
                if (w < 0)
                    w = -1;// 标志为 不可以 形成第i单词 到 第j单词的行，用 -1 作为标志位
                W[i][j] = w;
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (j >= i)
                    System.out.print(W[i][j] + "\t");
                else
                    System.out.print(" " + "\t");
            }
            System.out.println();
        }

        B[0] = W[0][0];
        for (int i = 1; i < len; i++) {
            B[i] = Integer.MAX_VALUE;
            for (int k = 1; k <= i; k++) {
                if (W[k][i] != -1) {
                    B[i] = Math.min(B[i], B[k - 1] + W[k][i]);
                    if (B[i] == B[k - 1] + W[k][i])
                        rowStartIndex[i] = k;
                }

            }

        }
        for (Integer c : rowStartIndex) {
            System.out.print(c + "\t");
        }
        return B[len - 1];
    }

    public static void main(String[] args) {
        PrintNeatly pN = new PrintNeatly();
        String[] word = {"First", "observe", "that", "the", "problem",
                "exhibits", "optimal", "substructure", "in",
                "the", "following", "way"};
        int[] l = {5, 7, 4, 3, 7, 8, 7, 12, 2, 3, 9, 3};
        int[] A = new int[]{4, 3, 2, 6, 4, 2, 3, 6};
        int M = 8;
        int result = pN.getNeatly(l, M);
        System.out.println("=======================================");
        System.out.println(result);
    }


}
